#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
#include <sstream>
#include <list>
#include <stack>
#include <queue>
using namespace std;

struct ListNode {
      int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
  };
 
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        cout << lists.size()<<endl;
        if(lists.size() < 1) return NULL;
        ListNode *rt = new ListNode(0);
        ListNode *p = rt;

        while(lists.size() > 0) { //还有数据没有参与排序
            int len = lists.size();
            int i =0,posi = 0,min = 0;
            if(lists[0] == NULL){
                lists.erase(lists.begin());
                continue;
            }
            min = lists[0]->val;
            for(i = 0;i<len;i++){ //获取每个链表的第一个元素的值
                if(lists[i] == NULL )continue;
                if(min > lists[i]->val ){
                    min = lists[i]->val;
                    posi = i;
                }
            }
            p->next = new ListNode(min);
            p = p->next;
            if(lists[posi]->next == NULL){
                lists.erase(lists.begin()+posi);
            } else {
                lists[posi] = lists[posi]->next ;
            }
        }
        return rt->next;
    }

    //两个升序链表排序
    ListNode* mergeTowList(ListNode *a, ListNode *b){
        if(!a || !b ) return a?a:b;
        ListNode *p1 = a,*p2 = b;
        ListNode *rt = new ListNode(0);
        ListNode *ptr = rt;
        while(p1 && p2){
            if(p1->val < p2->val) {
                ptr->next = p1;
                p1 = p1->next;
            } else {
                ptr->next = p2;
                p2 = p2->next;
            }
            ptr = ptr->next; 
        }
        ptr->next = p1 ? p1 : p2;
        return rt->next;
    }
    //归并
    ListNode* merge(vector<ListNode *>&lists,int left, int right) {
        if( left == right ) return lists[left];
        if(  left > right ) return nullptr;
        int mid = ( left + right ) >> 1;//求中值
        return mergeTowList( merge(lists , left , mid ) , merge(lists,mid + 1, right )) ;

    }

    ListNode* mergeKLists2(vector<ListNode*>& lists) {
        return merge(lists, 0 , lists.size() - 1);
    }

    //方法3：优先队列
    struct Status {
        int val ;
        ListNode *ptr;
        bool operator < (const Status &rhs) const {
            return val > rhs.val;
        }
    };
    priority_queue <Status> q;
    ListNode* mergeKLists3(vector<ListNode*>& lists) {
        for (auto node: lists) {
            if (node) q.push({node->val, node});
        }
        ListNode head, *tail = &head;
        while (!q.empty()) {
            auto f = q.top(); q.pop();
            tail->next = f.ptr; 
            tail = tail->next;
            if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});
        }
        return head.next;
    }

};


int main(){

    vector < vector<int> > ans;
    Solution sp;
    ListNode *l1 = new ListNode(1,new ListNode(4,new ListNode(5)));
    ListNode *l2 = new ListNode(1,new ListNode(3,new ListNode(4)));
    ListNode *l3 = new ListNode(2,new ListNode(6));

    vector<ListNode *> nums = { l1,l2,l3};
    
    //cout<<  sp.mergeKLists(nums) <<endl;
    ListNode *p = sp.mergeKLists3(nums);
    while( p ){
        cout<< p->val <<"->";
        p = p->next;
    };
    return 0;
}